Przedziały
Limit pamięci: 32 MB
Dany jest zbiór liczb całkowitych
.
Dla
i
całkowitych,
,
przedziałem
nazywamy zbiór kolejnych liczb całkowitych od
do
:
.
Rozbiciem zbioru
na przedziały nazywamy taki ciąg parami rozłącznych przedziałów,
że suma tych przedziałów daje zbiór
.
Twoim zadaniem jest napisać losowy generator rozbić zbioru
na przedziały.
Generator będzie działał w sposób iteracyjny.
W danym momencie pamiętamy zbiór liczb całkowitych, które są w
,
a nie zostały użyte jeszcze w żadnym przedziale.
Zaczynamy od całego zbioru
.
Następnie w każdej iteracji losujemy jakiś przedział i usuwamy go ze zbioru.
Postępujemy tak dopóki pamiętany zbiór nie jest pusty.
Losowanie przedziału należy wykonać jak następuje.
Mamy pewien podzbiór zbioru
.
Oznaczmy go przez
.
Wylosowany przedział musi się zawierać w
.
Numerujemy wszystkie przedziały, które się zawierają w
, od zera
w kolejności leksykograficznej względem początku i końca przedziału.
Np. dla
kolejne przedziały to:
i mają one odpowiednio numery
.
Wybór przedziału dokonujemy przez wylosowanie numerka.
Numerek losuje sprawdzaczka.
Komunikacja wejścia/wyjścia ze sprawdzaczką
Twój program powinien działać według następującego schematu.
Najpierw należy wczytać jedną liczbę całkowitą
,
.
Następnie należy zainicjować
.
Teraz, dopóki
, należy wykonywać kolejne iteracje.
W pojedynczej iteracji należy:
- wypisać na standardowe wyjście liczbę przedziałów
zawierających się w
,
- wczytać ze standardowego wejścia liczbę całkowitą
,
,
oznaczającą numerek wygenerowanego przedziału,
- wypisać dwie liczby całkowite
i
oddzielone pojedynczym odstępem oznaczające
wybrany przedział
,
- usunąć przedział
ze zbioru
.
Przykład
Dla danych wejściowych:
5
6
2
0
poprawną odpowiedzią jest:
15
2 3
4
4 5
1
1 1
Autor zadania: Jakub Pawlewicz.